home *** CD-ROM | disk | FTP | other *** search
/ MacFormat 1995 July / macformat-026.iso / mac / Shareware City / Developers / berkeleydb1.73 / Berkeley_db / hash / hash_page.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-07-27  |  24.0 KB  |  1,017 lines  |  [TEXT/MPS ]
  1. /*-
  2.  * Copyright (c) 1990, 1993
  3.  *    The Regents of the University of California.  All rights reserved.
  4.  *
  5.  * This code is derived from software contributed to Berkeley by
  6.  * Margo Seltzer.
  7.  *
  8.  * Redistribution and use in source and binary forms, with or without
  9.  * modification, are permitted provided that the following conditions
  10.  * are met:
  11.  * 1. Redistributions of source code must retain the above copyright
  12.  *    notice, this list of conditions and the following disclaimer.
  13.  * 2. Redistributions in binary form must reproduce the above copyright
  14.  *    notice, this list of conditions and the following disclaimer in the
  15.  *    documentation and/or other materials provided with the distribution.
  16.  * 3. All advertising materials mentioning features or use of this software
  17.  *    must display the following acknowledgement:
  18.  *    This product includes software developed by the University of
  19.  *    California, Berkeley and its contributors.
  20.  * 4. Neither the name of the University nor the names of its contributors
  21.  *    may be used to endorse or promote products derived from this software
  22.  *    without specific prior written permission.
  23.  *
  24.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  25.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  26.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  27.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  28.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  29.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  30.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  31.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  32.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  33.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  34.  * SUCH DAMAGE.
  35.  */
  36.  
  37. #if defined(LIBC_SCCS) && !defined(lint)
  38. static char sccsid[] = "@(#)hash_page.c    8.2 (Berkeley) 9/6/93";
  39. #endif /* LIBC_SCCS and not lint */
  40.  
  41. #if defined(macintosh) && (defined(powerc) || defined(__powerc))
  42. #include "OurMalloc.h"
  43. #endif
  44.  
  45. /*
  46.  * PACKAGE:  hashing
  47.  *
  48.  * DESCRIPTION:
  49.  *    Page manipulation for hashing package.
  50.  *
  51.  * ROUTINES:
  52.  *
  53.  * External
  54.  *    __get_page
  55.  *    __add_ovflpage
  56.  * Internal
  57.  *    overflow_page
  58.  *    open_temp
  59.  */
  60.  
  61. #include <sys/types.h>
  62.  
  63. #include <errno.h>
  64. #include <fcntl.h>
  65. #include <signal.h>
  66. #include <stdio.h>
  67. #include <stdlib.h>
  68. #include <string.h>
  69. #include <unistd.h>
  70. #ifdef DEBUG
  71. #include <assert.h>
  72. #endif
  73.  
  74. #ifdef macintosh
  75. #include <machine/endian.h>
  76. #include <sys/errno.h>
  77. #endif
  78.  
  79. #include <db.h>
  80. #include "hash.h"
  81. #include "page.h"
  82. #include "extern.h"
  83.  
  84. static u_long    *fetch_bitmap __P((HTAB *, int));
  85. static u_long     first_free __P((u_long));
  86. static int     open_temp __P((HTAB *));
  87. static u_short     overflow_page __P((HTAB *));
  88. static void     putpair __P((char *, const DBT *, const DBT *));
  89. static void     squeeze_key __P((u_short *, const DBT *, const DBT *));
  90. static int     ugly_split
  91.             __P((HTAB *, u_int, BUFHEAD *, BUFHEAD *, int, int));
  92.  
  93. #define    PAGE_INIT(P) { \
  94.     ((u_short *)(P))[0] = 0; \
  95.     ((u_short *)(P))[1] = hashp->BSIZE - 3 * sizeof(u_short); \
  96.     ((u_short *)(P))[2] = hashp->BSIZE; \
  97. }
  98.  
  99. /*
  100.  * This is called AFTER we have verified that there is room on the page for
  101.  * the pair (PAIRFITS has returned true) so we go right ahead and start moving
  102.  * stuff on.
  103.  */
  104. static void
  105. putpair(p, key, val)
  106.     char *p;
  107.     const DBT *key, *val;
  108. {
  109.     register u_short *bp, n, off;
  110.  
  111.     bp = (u_short *)p;
  112.  
  113.     /* Enter the key first. */
  114.     n = bp[0];
  115.  
  116.     off = OFFSET(bp) - key->size;
  117.     memmove(p + off, key->data, key->size);
  118.     bp[++n] = off;
  119.  
  120.     /* Now the data. */
  121.     off -= val->size;
  122.     memmove(p + off, val->data, val->size);
  123.     bp[++n] = off;
  124.  
  125.     /* Adjust page info. */
  126.     bp[0] = n;
  127.     bp[n + 1] = off - ((n + 3) * sizeof(u_short));
  128.     bp[n + 2] = off;
  129. }
  130.  
  131. /*
  132.  * Returns:
  133.  *     0 OK
  134.  *    -1 error
  135.  */
  136. extern int
  137. __delpair(hashp, bufp, ndx)
  138.     HTAB *hashp;
  139.     BUFHEAD *bufp;
  140.     register int ndx;
  141. {
  142.     register u_short *bp, newoff;
  143.     register int n;
  144.     u_short pairlen;
  145.  
  146.     bp = (u_short *)bufp->page;
  147.     n = bp[0];
  148.  
  149.     if (bp[ndx + 1] < REAL_KEY)
  150.         return (__big_delete(hashp, bufp));
  151.     if (ndx != 1)
  152.         newoff = bp[ndx - 1];
  153.     else
  154.         newoff = hashp->BSIZE;
  155.     pairlen = newoff - bp[ndx + 1];
  156.  
  157.     if (ndx != (n - 1)) {
  158.         /* Hard Case -- need to shuffle keys */
  159.         register int i;
  160.         register char *src = bufp->page + (int)OFFSET(bp);
  161.         register char *dst = src + (int)pairlen;
  162.         memmove(dst, src, bp[ndx + 1] - OFFSET(bp));
  163.  
  164.         /* Now adjust the pointers */
  165.         for (i = ndx + 2; i <= n; i += 2) {
  166.             if (bp[i + 1] == OVFLPAGE) {
  167.                 bp[i - 2] = bp[i];
  168.                 bp[i - 1] = bp[i + 1];
  169.             } else {
  170.                 bp[i - 2] = bp[i] + pairlen;
  171.                 bp[i - 1] = bp[i + 1] + pairlen;
  172.             }
  173.         }
  174.     }
  175.     /* Finally adjust the page data */
  176.     bp[n] = OFFSET(bp) + pairlen;
  177.     bp[n - 1] = bp[n + 1] + pairlen + 2 * sizeof(u_short);
  178.     bp[0] = n - 2;
  179.     hashp->NKEYS--;
  180.  
  181.     bufp->flags |= BUF_MOD;
  182.     return (0);
  183. }
  184. /*
  185.  * Returns:
  186.  *     0 ==> OK
  187.  *    -1 ==> Error
  188.  */
  189. extern int
  190. __split_page(hashp, obucket, nbucket)
  191.     HTAB *hashp;
  192.     u_int obucket, nbucket;
  193. {
  194.     register BUFHEAD *new_bufp, *old_bufp;
  195.     register u_short *ino;
  196.     register char *np;
  197.     DBT key, val;
  198.     int n, ndx, retval;
  199.     u_short copyto, diff, off, moved;
  200.     char *op;
  201.  
  202.     copyto = (u_short)hashp->BSIZE;
  203.     off = (u_short)hashp->BSIZE;
  204.     old_bufp = __get_buf(hashp, obucket, NULL, 0);
  205.     if (old_bufp == NULL)
  206.         return (-1);
  207.     new_bufp = __get_buf(hashp, nbucket, NULL, 0);
  208.     if (new_bufp == NULL)
  209.         return (-1);
  210.  
  211.     old_bufp->flags |= (BUF_MOD | BUF_PIN);
  212.     new_bufp->flags |= (BUF_MOD | BUF_PIN);
  213.  
  214.     ino = (u_short *)(op = old_bufp->page);
  215.     np = new_bufp->page;
  216.  
  217.     moved = 0;
  218.  
  219.     for (n = 1, ndx = 1; n < ino[0]; n += 2) {
  220.         if (ino[n + 1] < REAL_KEY) {
  221.             retval = ugly_split(hashp, obucket, old_bufp, new_bufp,
  222.                 (int)copyto, (int)moved);
  223.             old_bufp->flags &= ~BUF_PIN;
  224.             new_bufp->flags &= ~BUF_PIN;
  225.             return (retval);
  226.  
  227.         }
  228.         key.data = (u_char *)op + ino[n];
  229.         key.size = off - ino[n];
  230.  
  231.         if (__call_hash(hashp, key.data, key.size) == obucket) {
  232.             /* Don't switch page */
  233.             diff = copyto - off;
  234.             if (diff) {
  235.                 copyto = ino[n + 1] + diff;
  236.                 memmove(op + copyto, op + ino[n + 1],
  237.                     off - ino[n + 1]);
  238.                 ino[ndx] = copyto + ino[n] - ino[n + 1];
  239.                 ino[ndx + 1] = copyto;
  240.             } else
  241.                 copyto = ino[n + 1];
  242.             ndx += 2;
  243.         } else {
  244.             /* Switch page */
  245.             val.data = (u_char *)op + ino[n + 1];
  246.             val.size = ino[n] - ino[n + 1];
  247.             putpair(np, &key, &val);
  248.             moved += 2;
  249.         }
  250.  
  251.         off = ino[n + 1];
  252.     }
  253.  
  254.     /* Now clean up the page */
  255.     ino[0] -= moved;
  256.     FREESPACE(ino) = copyto - sizeof(u_short) * (ino[0] + 3);
  257.     OFFSET(ino) = copyto;
  258.  
  259. #ifdef DEBUG3
  260.     (void)fprintf(stderr, "split %d/%d\n",
  261.         ((u_short *)np)[0] / 2,
  262.         ((u_short *)op)[0] / 2);
  263. #endif
  264.     /* unpin both pages */
  265.     old_bufp->flags &= ~BUF_PIN;
  266.     new_bufp->flags &= ~BUF_PIN;
  267.     return (0);
  268. }
  269.  
  270. /*
  271.  * Called when we encounter an overflow or big key/data page during split
  272.  * handling.  This is special cased since we have to begin checking whether
  273.  * the key/data pairs fit on their respective pages and because we may need
  274.  * overflow pages for both the old and new pages.
  275.  *
  276.  * The first page might be a page with regular key/data pairs in which case
  277.  * we have a regular overflow condition and just need to go on to the next
  278.  * page or it might be a big key/data pair in which case we need to fix the
  279.  * big key/data pair.
  280.  *
  281.  * Returns:
  282.  *     0 ==> success
  283.  *    -1 ==> failure
  284.  */
  285. static int
  286. ugly_split(hashp, obucket, old_bufp, new_bufp, copyto, moved)
  287.     HTAB *hashp;
  288.     u_int obucket;    /* Same as __split_page. */
  289.     BUFHEAD *old_bufp, *new_bufp;
  290.     int copyto;    /* First byte on page which contains key/data values. */
  291.     int moved;    /* Number of pairs moved to new page. */
  292. {
  293.     register BUFHEAD *bufp;    /* Buffer header for ino */
  294.     register u_short *ino;    /* Page keys come off of */
  295.     register u_short *np;    /* New page */
  296.     register u_short *op;    /* Page keys go on to if they aren't moving */
  297.  
  298.     BUFHEAD *last_bfp;    /* Last buf header OVFL needing to be freed */
  299.     DBT key, val;
  300.     SPLIT_RETURN ret;
  301.     u_short n, off, ov_addr, scopyto;
  302.     char *cino;        /* Character value of ino */
  303.  
  304.     bufp = old_bufp;
  305.     ino = (u_short *)old_bufp->page;
  306.     np = (u_short *)new_bufp->page;
  307.     op = (u_short *)old_bufp->page;
  308.     last_bfp = NULL;
  309.     scopyto = (u_short)copyto;    /* ANSI */
  310.  
  311.     n = ino[0] - 1;
  312.     while (n < ino[0]) {
  313.         if (ino[2] < REAL_KEY && ino[2] != OVFLPAGE) {
  314.             if (__big_split(hashp, old_bufp,
  315.                 new_bufp, bufp, bufp->addr, obucket, &ret))
  316.                 return (-1);
  317.             old_bufp = ret.oldp;
  318.             if (!old_bufp)
  319.                 return (-1);
  320.             op = (u_short *)old_bufp->page;
  321.             new_bufp = ret.newp;
  322.             if (!new_bufp)
  323.                 return (-1);
  324.             np = (u_short *)new_bufp->page;
  325.             bufp = ret.nextp;
  326.             if (!bufp)
  327.                 return (0);
  328.             cino = (char *)bufp->page;
  329.             ino = (u_short *)cino;
  330.             last_bfp = ret.nextp;
  331.         } else if (ino[n + 1] == OVFLPAGE) {
  332.             ov_addr = ino[n];
  333.             /*
  334.              * Fix up the old page -- the extra 2 are the fields
  335.              * which contained the overflow information.
  336.              */
  337.             ino[0] -= (moved + 2);
  338.             FREESPACE(ino) =
  339.                 scopyto - sizeof(u_short) * (ino[0] + 3);
  340.             OFFSET(ino) = scopyto;
  341.  
  342.             bufp = __get_buf(hashp, ov_addr, bufp, 0);
  343.             if (!bufp)
  344.                 return (-1);
  345.  
  346.             ino = (u_short *)bufp->page;
  347.             n = 1;
  348.             scopyto = hashp->BSIZE;
  349.             moved = 0;
  350.  
  351.             if (last_bfp)
  352.                 __free_ovflpage(hashp, last_bfp);
  353.             last_bfp = bufp;
  354.         }
  355.         /* Move regular sized pairs of there are any */
  356.         off = hashp->BSIZE;
  357.         for (n = 1; (n < ino[0]) && (ino[n + 1] >= REAL_KEY); n += 2) {
  358.             cino = (char *)ino;
  359.             key.data = (u_char *)cino + ino[n];
  360.             key.size = off - ino[n];
  361.             val.data = (u_char *)cino + ino[n + 1];
  362.             val.size = ino[n] - ino[n + 1];
  363.             off = ino[n + 1];
  364.  
  365.             if (__call_hash(hashp, key.data, key.size) == obucket) {
  366.                 /* Keep on old page */
  367.                 if (PAIRFITS(op, (&key), (&val)))
  368.                     putpair((char *)op, &key, &val);
  369.                 else {
  370.                     old_bufp =
  371.                         __add_ovflpage(hashp, old_bufp);
  372.                     if (!old_bufp)
  373.                         return (-1);
  374.                     op = (u_short *)old_bufp->page;
  375.                     putpair((char *)op, &key, &val);
  376.                 }
  377.                 old_bufp->flags |= BUF_MOD;
  378.             } else {
  379.                 /* Move to new page */
  380.                 if (PAIRFITS(np, (&key), (&val)))
  381.                     putpair((char *)np, &key, &val);
  382.                 else {
  383.                     new_bufp =
  384.                         __add_ovflpage(hashp, new_bufp);
  385.                     if (!new_bufp)
  386.                         return (-1);
  387.                     np = (u_short *)new_bufp->page;
  388.                     putpair((char *)np, &key, &val);
  389.                 }
  390.                 new_bufp->flags |= BUF_MOD;
  391.             }
  392.         }
  393.     }
  394.     if (last_bfp)
  395.         __free_ovflpage(hashp, last_bfp);
  396.     return (0);
  397. }
  398.  
  399. /*
  400.  * Add the given pair to the page
  401.  *
  402.  * Returns:
  403.  *    0 ==> OK
  404.  *    1 ==> failure
  405.  */
  406. extern int
  407. __addel(hashp, bufp, key, val)
  408.     HTAB *hashp;
  409.     BUFHEAD *bufp;
  410.     const DBT *key, *val;
  411. {
  412.     register u_short *bp, *sop;
  413.     int do_expand;
  414.  
  415.     bp = (u_short *)bufp->page;
  416.     do_expand = 0;
  417.     while (bp[0] && (bp[2] < REAL_KEY || bp[bp[0]] < REAL_KEY))
  418.         /* Exception case */
  419.         if (bp[2] == FULL_KEY_DATA && bp[0] == 2)
  420.             /* This is the last page of a big key/data pair
  421.                and we need to add another page */
  422.             break;
  423.         else if (bp[2] < REAL_KEY && bp[bp[0]] != OVFLPAGE) {
  424.             bufp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0);
  425.             if (!bufp)
  426.                 return (-1);
  427.             bp = (u_short *)bufp->page;
  428.         } else
  429.             /* Try to squeeze key on this page */
  430.             if (FREESPACE(bp) > PAIRSIZE(key, val)) {
  431.                 squeeze_key(bp, key, val);
  432.                 return (0);
  433.             } else {
  434.                 bufp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0);
  435.                 if (!bufp)
  436.                     return (-1);
  437.                 bp = (u_short *)bufp->page;
  438.             }
  439.  
  440.     if (PAIRFITS(bp, key, val))
  441.         putpair(bufp->page, key, val);
  442.     else {
  443.         do_expand = 1;
  444.         bufp = __add_ovflpage(hashp, bufp);
  445.         if (!bufp)
  446.             return (-1);
  447.         sop = (u_short *)bufp->page;
  448.  
  449.         if (PAIRFITS(sop, key, val))
  450.             putpair((char *)sop, key, val);
  451.         else
  452.             if (__big_insert(hashp, bufp, key, val))
  453.                 return (-1);
  454.     }
  455.     bufp->flags |= BUF_MOD;
  456.     /*
  457.      * If the average number of keys per bucket exceeds the fill factor,
  458.      * expand the table.
  459.      */
  460.     hashp->NKEYS++;
  461.     if (do_expand ||
  462.         (hashp->NKEYS / (hashp->MAX_BUCKET + 1) > hashp->FFACTOR))
  463.         return (__expand_table(hashp));
  464.     return (0);
  465. }
  466.  
  467. /*
  468.  *
  469.  * Returns:
  470.  *    pointer on success
  471.  *    NULL on error
  472.  */
  473. extern BUFHEAD *
  474. __add_ovflpage(hashp, bufp)
  475.     HTAB *hashp;
  476.     BUFHEAD *bufp;
  477. {
  478.     register u_short *sp;
  479.     u_short ndx, ovfl_num;
  480. #ifdef DEBUG1
  481.     int tmp1, tmp2;
  482. #endif
  483.     sp = (u_short *)bufp->page;
  484.  
  485.     /* Check if we are dynamically determining the fill factor */
  486.     if (hashp->FFACTOR == DEF_FFACTOR) {
  487.         hashp->FFACTOR = sp[0] >> 1;
  488.         if (hashp->FFACTOR < MIN_FFACTOR)
  489.             hashp->FFACTOR = MIN_FFACTOR;
  490.     }
  491.     bufp->flags |= BUF_MOD;
  492.     ovfl_num = overflow_page(hashp);
  493. #ifdef DEBUG1
  494.     tmp1 = bufp->addr;
  495.     tmp2 = bufp->ovfl ? bufp->ovfl->addr : 0;
  496. #endif
  497.     if (!ovfl_num || !(bufp->ovfl = __get_buf(hashp, ovfl_num, bufp, 1)))
  498.         return (NULL);
  499.     bufp->ovfl->flags |= BUF_MOD;
  500. #ifdef DEBUG1
  501.     (void)fprintf(stderr, "ADDOVFLPAGE: %d->ovfl was %d is now %d\n",
  502.         tmp1, tmp2, bufp->ovfl->addr);
  503. #endif
  504.     ndx = sp[0];
  505.     /*
  506.      * Since a pair is allocated on a page only if there's room to add
  507.      * an overflow page, we know that the OVFL information will fit on
  508.      * the page.
  509.      */
  510.     sp[ndx + 4] = OFFSET(sp);
  511.     sp[ndx + 3] = FREESPACE(sp) - OVFLSIZE;
  512.     sp[ndx + 1] = ovfl_num;
  513.     sp[ndx + 2] = OVFLPAGE;
  514.     sp[0] = ndx + 2;
  515. #ifdef HASH_STATISTICS
  516.     hash_overflows++;
  517. #endif
  518.     return (bufp->ovfl);
  519. }
  520.  
  521. /*
  522.  * Returns:
  523.  *     0 indicates SUCCESS
  524.  *    -1 indicates FAILURE
  525.  */
  526. extern int
  527. __get_page(hashp, p, bucket, is_bucket, is_disk, is_bitmap)
  528.     HTAB *hashp;
  529.     char *p;
  530.     u_int bucket;
  531.     int is_bucket, is_disk, is_bitmap;
  532. {
  533.     register int fd, page, size;
  534.     int rsize;
  535.     u_short *bp;
  536.  
  537.     fd = hashp->fp;
  538.     size = hashp->BSIZE;
  539.  
  540.     if ((fd == -1) || !is_disk) {
  541.         PAGE_INIT(p);
  542.         return (0);
  543.     }
  544.     if (is_bucket)
  545.         page = BUCKET_TO_PAGE(bucket);
  546.     else
  547.         page = OADDR_TO_PAGE(bucket);
  548.     if ((lseek(fd, (off_t)page << hashp->BSHIFT, SEEK_SET) == -1) ||
  549.         ((rsize = read(fd, p, size)) == -1))
  550.         return (-1);
  551.     bp = (u_short *)p;
  552.     if (!rsize)
  553.         bp[0] = 0;    /* We hit the EOF, so initialize a new page */
  554.     else
  555.         if (rsize != size) {
  556.             errno = EFTYPE;
  557.             return (-1);
  558.         }
  559.     if (!is_bitmap && !bp[0]) {
  560.         PAGE_INIT(p);
  561.     } else
  562.         if (hashp->LORDER != BYTE_ORDER) {
  563.             register int i, max;
  564.  
  565.             if (is_bitmap) {
  566.                 max = hashp->BSIZE >> 2; /* divide by 4 */
  567.                 for (i = 0; i < max; i++)
  568.                     BLSWAP(((long *)p)[i]);
  569.             } else {
  570.                 BSSWAP(bp[0]);
  571.                 max = bp[0] + 2;
  572.                 for (i = 1; i <= max; i++)
  573.                     BSSWAP(bp[i]);
  574.             }
  575.         }
  576.     return (0);
  577. }
  578.  
  579. /*
  580.  * Write page p to disk
  581.  *
  582.  * Returns:
  583.  *     0 ==> OK
  584.  *    -1 ==>failure
  585.  */
  586. extern int
  587. __put_page(hashp, p, bucket, is_bucket, is_bitmap)
  588.     HTAB *hashp;
  589.     char *p;
  590.     u_int bucket;
  591.     int is_bucket, is_bitmap;
  592. {
  593.     register int fd, page, size;
  594.     int wsize;
  595.  
  596.     size = hashp->BSIZE;
  597.     if ((hashp->fp == -1) && open_temp(hashp))
  598.         return (-1);
  599.     fd = hashp->fp;
  600.  
  601.     if (hashp->LORDER != BYTE_ORDER) {
  602.         register int i;
  603.         register int max;
  604.  
  605.         if (is_bitmap) {
  606.             max = hashp->BSIZE >> 2;    /* divide by 4 */
  607.             for (i = 0; i < max; i++)
  608.                 BLSWAP(((long *)p)[i]);
  609.         } else {
  610.             max = ((u_short *)p)[0] + 2;
  611.             for (i = 0; i <= max; i++)
  612.                 BSSWAP(((u_short *)p)[i]);
  613.         }
  614.     }
  615.     if (is_bucket)
  616.         page = BUCKET_TO_PAGE(bucket);
  617.     else
  618.         page = OADDR_TO_PAGE(bucket);
  619.     if ((lseek(fd, (off_t)page << hashp->BSHIFT, SEEK_SET) == -1) ||
  620.         ((wsize = write(fd, p, size)) == -1))
  621.         /* Errno is set */
  622.         return (-1);
  623.     if (wsize != size) {
  624.         errno = EFTYPE;
  625.         return (-1);
  626.     }
  627.     return (0);
  628. }
  629.  
  630. #define BYTE_MASK    ((1 << INT_BYTE_SHIFT) -1)
  631. /*
  632.  * Initialize a new bitmap page.  Bitmap pages are left in memory
  633.  * once they are read in.
  634.  */
  635. extern int
  636. __init_bitmap(hashp, pnum, nbits, ndx)
  637.     HTAB *hashp;
  638.     int pnum, nbits, ndx;
  639. {
  640.     u_long *ip;
  641.     int clearbytes, clearints;
  642.  
  643.     if (!(ip = malloc(hashp->BSIZE)))
  644.         return (1);
  645.     hashp->nmaps++;
  646.     clearints = ((nbits - 1) >> INT_BYTE_SHIFT) + 1;
  647.     clearbytes = clearints << INT_TO_BYTE;
  648.     (void)memset((char *)ip, 0, clearbytes);
  649.     (void)memset(((char *)ip) + clearbytes, 0xFF,
  650.         hashp->BSIZE - clearbytes);
  651.     ip[clearints - 1] = ALL_SET << (nbits & BYTE_MASK);
  652.     SETBIT(ip, 0);
  653.     hashp->BITMAPS[ndx] = (u_short)pnum;
  654.     hashp->mapp[ndx] = ip;
  655.     return (0);
  656. }
  657.  
  658. static u_long
  659. first_free(map)
  660.     u_long map;
  661. {
  662.     register u_long i, mask;
  663.  
  664.     mask = 0x1;
  665.     for (i = 0; i < BITS_PER_MAP; i++) {
  666.         if (!(mask & map))
  667.             return (i);
  668.         mask = mask << 1;
  669.     }
  670.     return (i);
  671. }
  672.  
  673. static u_short
  674. overflow_page(hashp)
  675.     HTAB *hashp;
  676. {
  677.     register u_long *freep;
  678.     register int max_free, offset, splitnum;
  679.     u_short addr;
  680.     int bit, first_page, free_bit, free_page, i, in_use_bits, j;
  681. #ifdef DEBUG2
  682.     int tmp1, tmp2;
  683. #endif
  684.     splitnum = hashp->OVFL_POINT;
  685.     max_free = hashp->SPARES[splitnum];
  686.  
  687.     free_page = (max_free - 1) >> (hashp->BSHIFT + BYTE_SHIFT);
  688.     free_bit = (max_free - 1) & ((hashp->BSIZE << BYTE_SHIFT) - 1);
  689.  
  690.     /* Look through all the free maps to find the first free block */
  691.     first_page = hashp->LAST_FREED >>(hashp->BSHIFT + BYTE_SHIFT);
  692.     for ( i = first_page; i <= free_page; i++ ) {
  693.         if (!(freep = (u_long *)hashp->mapp[i]) &&
  694.             !(freep = fetch_bitmap(hashp, i)))
  695.             return (NULL);
  696.         if (i == free_page)
  697.             in_use_bits = free_bit;
  698.         else
  699.             in_use_bits = (hashp->BSIZE << BYTE_SHIFT) - 1;
  700.         
  701.         if (i == first_page) {
  702.             bit = hashp->LAST_FREED &
  703.                 ((hashp->BSIZE << BYTE_SHIFT) - 1);
  704.             j = bit / BITS_PER_MAP;
  705.             bit = bit & ~(BITS_PER_MAP - 1);
  706.         } else {
  707.             bit = 0;
  708.             j = 0;
  709.         }
  710.         for (; bit <= in_use_bits; j++, bit += BITS_PER_MAP)
  711.             if (freep[j] != ALL_SET)
  712.                 goto found;
  713.     }
  714.  
  715.     /* No Free Page Found */
  716.     hashp->LAST_FREED = hashp->SPARES[splitnum];
  717.     hashp->SPARES[splitnum]++;
  718.     offset = hashp->SPARES[splitnum] -
  719.         (splitnum ? hashp->SPARES[splitnum - 1] : 0);
  720.  
  721. #define    OVMSG    "HASH: Out of overflow pages.  Increase page size\n"
  722.     if (offset > SPLITMASK) {
  723.         if (++splitnum >= NCACHED) {
  724.             (void)write(STDERR_FILENO, OVMSG, sizeof(OVMSG) - 1);
  725.             return (NULL);
  726.         }
  727.         hashp->OVFL_POINT = splitnum;
  728.         hashp->SPARES[splitnum] = hashp->SPARES[splitnum-1];
  729.         hashp->SPARES[splitnum-1]--;
  730.         offset = 1;
  731.     }
  732.  
  733.     /* Check if we need to allocate a new bitmap page */
  734.     if (free_bit == (hashp->BSIZE << BYTE_SHIFT) - 1) {
  735.         free_page++;
  736.         if (free_page >= NCACHED) {
  737.             (void)write(STDERR_FILENO, OVMSG, sizeof(OVMSG) - 1);
  738.             return (NULL);
  739.         }
  740.         /*
  741.          * This is tricky.  The 1 indicates that you want the new page
  742.          * allocated with 1 clear bit.  Actually, you are going to
  743.          * allocate 2 pages from this map.  The first is going to be
  744.          * the map page, the second is the overflow page we were
  745.          * looking for.  The init_bitmap routine automatically, sets
  746.          * the first bit of itself to indicate that the bitmap itself
  747.          * is in use.  We would explicitly set the second bit, but
  748.          * don't have to if we tell init_bitmap not to leave it clear
  749.          * in the first place.
  750.          */
  751.         if (__init_bitmap(hashp, (int)OADDR_OF(splitnum, offset),
  752.             1, free_page))
  753.             return (NULL);
  754.         hashp->SPARES[splitnum]++;
  755. #ifdef DEBUG2
  756.         free_bit = 2;
  757. #endif
  758.         offset++;
  759.         if (offset > SPLITMASK) {
  760.             if (++splitnum >= NCACHED) {
  761.                 (void)write(STDERR_FILENO, OVMSG,
  762.                     sizeof(OVMSG) - 1);
  763.                 return (NULL);
  764.             }
  765.             hashp->OVFL_POINT = splitnum;
  766.             hashp->SPARES[splitnum] = hashp->SPARES[splitnum-1];
  767.             hashp->SPARES[splitnum-1]--;
  768.             offset = 0;
  769.         }
  770.     } else {
  771.         /*
  772.          * Free_bit addresses the last used bit.  Bump it to address
  773.          * the first available bit.
  774.          */
  775.         free_bit++;
  776.         SETBIT(freep, free_bit);
  777.     }
  778.  
  779.     /* Calculate address of the new overflow page */
  780.     addr = OADDR_OF(splitnum, offset);
  781. #ifdef DEBUG2
  782.     (void)fprintf(stderr, "OVERFLOW_PAGE: ADDR: %d BIT: %d PAGE %d\n",
  783.         addr, free_bit, free_page);
  784. #endif
  785.     return (addr);
  786.  
  787. found:
  788.     bit = bit + first_free(freep[j]);
  789.     SETBIT(freep, bit);
  790. #ifdef DEBUG2
  791.     tmp1 = bit;
  792.     tmp2 = i;
  793. #endif
  794.     /*
  795.      * Bits are addressed starting with 0, but overflow pages are addressed
  796.      * beginning at 1. Bit is a bit addressnumber, so we need to increment
  797.      * it to convert it to a page number.
  798.      */
  799.     bit = 1 + bit + (i * (hashp->BSIZE << BYTE_SHIFT));
  800.     if (bit >= hashp->LAST_FREED)
  801.         hashp->LAST_FREED = bit - 1;
  802.  
  803.     /* Calculate the split number for this page */
  804.     for (i = 0; (i < splitnum) && (bit > hashp->SPARES[i]); i++);
  805.     offset = (i ? bit - hashp->SPARES[i - 1] : bit);
  806.     if (offset >= SPLITMASK)
  807.         return (NULL);    /* Out of overflow pages */
  808.     addr = OADDR_OF(i, offset);
  809. #ifdef DEBUG2
  810.     (void)fprintf(stderr, "OVERFLOW_PAGE: ADDR: %d BIT: %d PAGE %d\n",
  811.         addr, tmp1, tmp2);
  812. #endif
  813.  
  814.     /* Allocate and return the overflow page */
  815.     return (addr);
  816. }
  817.  
  818. /*
  819.  * Mark this overflow page as free.
  820.  */
  821. extern void
  822. __free_ovflpage(hashp, obufp)
  823.     HTAB *hashp;
  824.     BUFHEAD *obufp;
  825. {
  826.     register u_short addr;
  827.     u_long *freep;
  828.     int bit_address, free_page, free_bit;
  829.     u_short ndx;
  830.  
  831.     addr = obufp->addr;
  832. #ifdef DEBUG1
  833.     (void)fprintf(stderr, "Freeing %d\n", addr);
  834. #endif
  835.     ndx = (((u_short)addr) >> SPLITSHIFT);
  836.     bit_address =
  837.         (ndx ? hashp->SPARES[ndx - 1] : 0) + (addr & SPLITMASK) - 1;
  838.      if (bit_address < hashp->LAST_FREED)
  839.         hashp->LAST_FREED = bit_address;
  840.     free_page = (bit_address >> (hashp->BSHIFT + BYTE_SHIFT));
  841.     free_bit = bit_address & ((hashp->BSIZE << BYTE_SHIFT) - 1);
  842.  
  843.     if (!(freep = hashp->mapp[free_page]))
  844.         freep = fetch_bitmap(hashp, free_page);
  845. #ifdef DEBUG
  846.     /*
  847.      * This had better never happen.  It means we tried to read a bitmap
  848.      * that has already had overflow pages allocated off it, and we
  849.      * failed to read it from the file.
  850.      */
  851.     if (!freep)
  852.         assert(0);
  853. #endif
  854.     CLRBIT(freep, free_bit);
  855. #ifdef DEBUG2
  856.     (void)fprintf(stderr, "FREE_OVFLPAGE: ADDR: %d BIT: %d PAGE %d\n",
  857.         obufp->addr, free_bit, free_page);
  858. #endif
  859.     __reclaim_buf(hashp, obufp);
  860. }
  861.  
  862. /*
  863.  * Returns:
  864.  *     0 success
  865.  *    -1 failure
  866.  */
  867. #ifdef macintosh
  868. #include <Files.h>
  869. #include <Folders.h>
  870. #include <TFileSpec.h>
  871. #include <Errors.h>
  872.  
  873. typedef struct tfdsc {
  874.     struct tfdsc *    next;
  875.     FSSpec            spec;
  876. } tfdsc;
  877.  
  878. static tfdsc * tempdescs = 0;
  879.  
  880. static void closedescs()
  881. {
  882.     while (tempdescs) {
  883.         HDelete(tempdescs->spec.vRefNum, tempdescs->spec.parID, tempdescs->spec.name);
  884.         
  885.         tempdescs = tempdescs->next;
  886.     }
  887. }
  888.  
  889. /* Create a temporary file in the temp folder. 
  890. */
  891. static int
  892. open_temp(hashp)
  893.     HTAB *hashp;
  894. {
  895.     static int    id    =    0;
  896.     FSSpec        desc;
  897.     OSErr            err;
  898.     tfdsc *        nudsc;
  899.     
  900.     if (err = FindFolder(kOnSystemDisk, 'temp', true, &desc.vRefNum, &desc.parID))
  901.         return -1;
  902.     
  903.     *((long *) desc.name)        =    '\007tmp';
  904.     
  905.     do {
  906.         desc.name[4]    =    id / 1000     % 10 + '0';
  907.         desc.name[5]    =    id / 100        % 10 + '0';
  908.         desc.name[6]    =    id / 10        % 10 + '0';
  909.         desc.name[7]    =    id             % 10 + '0';
  910.         
  911.         ++id;
  912.         
  913.         err = HCreate(desc.vRefNum, desc.parID, desc.name, 'TEMP', 'TEXT');
  914.     } while (err == dupFNErr);
  915.     
  916.     hashp->fp = open(FSp2FullPath(&desc), O_RDWR);
  917.     
  918.     if (hashp->fp < 0)
  919.         return hashp->fp;
  920.     
  921.     if (!tempdescs)
  922.         atexit(closedescs);
  923.     
  924.     nudsc = malloc(sizeof(tfdsc));
  925.     
  926.     nudsc->next = tempdescs;
  927.     nudsc->spec = desc;
  928.     tempdescs     = nudsc;
  929.     
  930.     return 0;
  931. }
  932. #else
  933. static int
  934. open_temp(hashp)
  935.     HTAB *hashp;
  936. {
  937.     sigset_t set, oset;
  938.     static char namestr[] = "_hashXXXXXX";
  939.  
  940.     /* Block signals; make sure file goes away at process exit. */
  941.     (void)sigfillset(&set);
  942.     (void)sigprocmask(SIG_BLOCK, &set, &oset);
  943.     if ((hashp->fp = mkstemp(namestr)) != -1) {
  944.         (void)unlink(namestr);
  945.         (void)fcntl(hashp->fp, F_SETFD, 1);
  946.     }
  947.     (void)sigprocmask(SIG_SETMASK, &oset, (sigset_t *)NULL);
  948.     return (hashp->fp != -1 ? 0 : -1);
  949. }
  950. #endif
  951.  
  952. /*
  953.  * We have to know that the key will fit, but the last entry on the page is
  954.  * an overflow pair, so we need to shift things.
  955.  */
  956. static void
  957. squeeze_key(sp, key, val)
  958.     u_short *sp;
  959.     const DBT *key, *val;
  960. {
  961.     register char *p;
  962.     u_short free_space, n, off, pageno;
  963.  
  964.     p = (char *)sp;
  965.     n = sp[0];
  966.     free_space = FREESPACE(sp);
  967.     off = OFFSET(sp);
  968.  
  969.     pageno = sp[n - 1];
  970.     off -= key->size;
  971.     sp[n - 1] = off;
  972.     memmove(p + off, key->data, key->size);
  973.     off -= val->size;
  974.     sp[n] = off;
  975.     memmove(p + off, val->data, val->size);
  976.     sp[0] = n + 2;
  977.     sp[n + 1] = pageno;
  978.     sp[n + 2] = OVFLPAGE;
  979.     FREESPACE(sp) = free_space - PAIRSIZE(key, val);
  980.     OFFSET(sp) = off;
  981. }
  982.  
  983. static u_long *
  984. fetch_bitmap(hashp, ndx)
  985.     HTAB *hashp;
  986.     int ndx;
  987. {
  988.     if (ndx >= hashp->nmaps ||
  989.         !(hashp->mapp[ndx] = malloc(hashp->BSIZE)) ||
  990.         __get_page(hashp, (char *)hashp->mapp[ndx],
  991.         hashp->BITMAPS[ndx], 0, 1, 1))
  992.         return (NULL);
  993.     return (hashp->mapp[ndx]);
  994. }
  995.  
  996. #ifdef DEBUG4
  997. int
  998. print_chain(addr)
  999.     int addr;
  1000. {
  1001.     BUFHEAD *bufp;
  1002.     short *bp, oaddr;
  1003.  
  1004.     (void)fprintf(stderr, "%d ", addr);
  1005.     bufp = __get_buf(hashp, addr, NULL, 0);
  1006.     bp = (short *)bufp->page;
  1007.     while (bp[0] && ((bp[bp[0]] == OVFLPAGE) ||
  1008.         ((bp[0] > 2) && bp[2] < REAL_KEY))) {
  1009.         oaddr = bp[bp[0] - 1];
  1010.         (void)fprintf(stderr, "%d ", (int)oaddr);
  1011.         bufp = __get_buf(hashp, (int)oaddr, bufp, 0);
  1012.         bp = (short *)bufp->page;
  1013.     }
  1014.     (void)fprintf(stderr, "\n");
  1015. }
  1016. #endif
  1017.